This specification relates to caching for storage devices based on spatial distribution of accesses to the data storage devices.
Examples of storage devices include hard disk drives and optical disc drives. Storage devices typically store data in blocks on a rotating storage medium. Block sizes are often measured in kilobytes (KB). For example, the storage medium may include magnetic disks, optical discs, etc. Therefore, the storage devices typically have slower access times than semiconductor memory. As a result, data can be read faster from the semiconductor memory than from the storage medium.
Many storage devices include a semiconductor memory called cache memory to store data that is repeatedly requested by a host or that may be requested by the host. Such storage devices typically include a cache controller that controls caching of data to the cache memory. For example, when the host issues a read command, the cache controller first determines if the requested data is available in the cache memory. If not, a cache miss occurs, and the data is retrieved from the storage medium and is forwarded to the host. The cache controller may cache the data in the cache memory.
When the host requests the same data again, the data is found in the cache memory (i.e., a cache hit occurs) and is output to the host from the cache memory. The host receives the data faster from the cache memory than from the storage medium. Additionally, based on the data requested by the host, other related data may be cached in anticipation that the host may request the other related data. The size of the cache memory, however, is limited. Accordingly, the amount of data that can be cached is also limited. Therefore, the cache controller may selectively delete data from the cache memory. For example, data not requested by the host for a period of time may be deleted from the cache memory. Data may also be deleted when the host requests different data than the data stored in the cache memory. By selectively deleting data from the cache memory, data that is more likely to be used by the host can be cached.